Chapter 5: Functions: More Advanced Concepts
From book Python Programming (Problem solving, Packages and Libraries) published by McGraw Hill Education (India) Private limited.
By:
Note the following:-
>>> symbol and therefore cannot be directly executed. If you want to execute them on IDLE or Jupyter, you need to manually remove the >>> symbol.Markdown and code cells (extension .ipynb) and then downloaded as html. If someone wants to "modify" or "extend' this document, you may ask for the original .ipynb file by sending me an e-mail at:- 999.anuraggupta@gmail.com5.2. Passing variables in a function call
In Python, both “call by value” and “call by refrenced” are possible. Which particular scheme will be used depends upon the “type of object” being passed to a function call as parameter. This will become clear from the following examples:
def f(z):
if type(z) is int:
print('z is an integer so passed by value')
print('Initially z is->', z)
z = 4
print('Now z is->', z)
elif type(z) is list:
print('z is a list so passed by reference')
print('Initially z is->', z)
z.append(1)
print('Now z is->', z)
a = 5
f(a)# Call function f(a) giving it a integer as parameter
c = [5,4,3]
f(c)# Call function f(a) giving it a list as parameter
print('After the function call a is-> ', a)
print('After the function call c is-> ', c)
5.3.1. Providing default arguments or parameter values
Advantages of providing “default values” to parameters in a function definition are as follows:
This will be clear from following example:
def f( a ='A', b ='B'): # Default for a is “A”, for b is “B”
print(a, b)
f(1,2)
f(3) # Default value for b ie 'B' is taken, since only 1 parameter provide
f() # Default values for both a and b taken, since no parameter provided
Rules for default values are as follows:
This will be clear from the following def statements:
def f1(a=1, b=2, c=3): #OK
pass
def f2(a,b, c=3): #OK
pass
def f3(a, b =2, c =3): #OK
pass
def f4(a =1, b,c): #Error
pass
def f5(a, b= 2, c): #Error
pass
Default parameters are evaluated as the function is executed. This “evaluation” of values for default parameter is done only once, when the function is first called.
However, if the function is called repeatedly, then the same “pre-computed” value is used for each call.
Note that under normal circumstances this does not matter. However, this will matter if you use a mutable object, such as a list for a default argument as shown below:
def fAdd(a =1, b = []):
b.append(a)
return b
L1 = fAdd(5)
print(L1)
L2 = fAdd(6) # Here default value of b is [5] not []
print(L2)
5.3.2. Passing of arguments by position
Passing of arguments by position is discussed here and by keyword in the next section. When you call a function, the function definition will normally expect two things:
For instance, if you have:
def f(a,b,c='cat', d= 'dog'):
pass
f('ant', 'bee') # OK
f('A', 'B', 'C') #OK
f(1,2,3,4) #OK
f(1) # ERROR because you must provide at least 2 arguments ie for a and b
f() # Error
5.3.3. Keyword arguments
In the previous section, there was a discussion on how arguments could be passed by position. This scheme has one drawback.
Suppose you have a scenario where you don’t want to follow the “order” of passing of parameters or you want to skip some parameters in between and then pass those at the end of the list. In some programming languages, this is possible.
For instance, in some programming languages you can use the syntax f(a, , b,c) where the two consecutive commas indicate a missing parameter . You cannot do this in Python.
In Python, a technique called “keyword arguments” is used instead.
In this scheme, while “passing” the arguments from the function call to the function definition, one uses the “keywords” or the “names” of the arguments in the function definition to tell the function definition which parameter from the function call is linked to which parameter in the function definition.
This will be clear from the following example:
def f1(a, b, c):
print('a->', a, 'b->', b, 'c->', c)
# Lets change order of arguments
f1(b = 2, c = 3, a = 1) # OK even though order of arguments changed
f1(c ='cat', b = 'bat', a = 'ant') # Again OK
5.3.4. Using both “default-values” and “keyword-arguments” together
The following script shows an example where both default values and “keyword-argument” pairs are used together.
As explained earlier, the default values are in the function definition, whereas the “keyword-argument” pairs are used in the function call:
def f1(a, b = 'BOY', c= 'CAT'): # Default values to b and c
print('a->', a, 'b->', b, 'c->', c)
f1('apple') #OK. Will use default values for b and c
f1(a= 'ant') # Also OK
f1(b = 'baby', a ='ass') # Will use default for 3rd parameter ie c = ‘ÇAT’
5.3.5. Using variable number of arguments in a function call by using the syntax with * in function definition
This is best understood by an example.
Suppose you want to write a function that adds up the numbers provided as arguments and returns the sum.
If you know the number of numbers to be added, there is no problem, but suppose you want to write a function which can add different “number of numbers”.
So, if this function was say f(), then it could add f(2,3) to give 5 and also f(2,3,4) to give 9 and f(2,3,4,5) to give 14 and so on.
In Python, you can do this using a special way of writing a function using an asterix ‘*’ before the argument, such as say f(*args)
def f(*arg): #Function def with *arg. Can give variable numbers of arguments.
total = 0
for x in arg:
total = total + x
return total
print (f(1,2,3,4)) # Call the function with 4 arguments
print(f(1,2)) # Call the function with 2 arguments
One can combine a fixed number of arguments to a variable number of arguments also.
For instance, you can write a general purpose function which can find the square (Raised to power 2), or Cube (Raised to power 3 ) or any other power of numbers supplied and then add these numbers to give the result.
Also, let the first parameter to the function call represent the power to which these numbers are to be raised. So f(2,1,2,3,4) means raise to power 2, the numbers 1,2,3,4 and add them.
So f(2,1,2,3,4) → 12 +22 + 32 + 42 → 30.
Similarly, f(3,2,3,4) → 23 + 33 + 43 → 99.
This can be done as follows:
def f(n, *args): #Function def with *arg. Can give variable numbers of arguments.
total = 0
for x in args:
total = total + x ** n
return total
print(f(2,1,2,3,4)) # Call the function with 1 fixed and 4 variable arguments
print(f(3,2,3,4)) # Call the function with 1 fixed and 3 variable arguments
`5.3.6.` Using `**kwarg` in function definition to pass a key worded, variable-length of arguments.
The above statement needs to be understood in detail. The various parts of the statement are explained as follows:
*arg that in *arg you provide only one value for each argument, whereas in `**kwarg` you provide two values, one for the key and other for its value. kwarg’ is just by convention, one can use any valid Python name. The above concepts will be clear from the following examples:
def f(**kwargs):
for k, v in kwargs.items(): # k will hold the key and v will hold the value
print('Value of->', k, "is->", v)
# Using keyword pair as arguments to function call
f(lion = "Roar", bird = "chirp")
#Using a dictionary with ** as parameter to the function call
d1 = {"cat" : "meow", "dog" : "bark", "horse" : "neigh"}
f(**d1)
It was mentioned that within a function definition `*arg` acts like a tuple and **`kwarg` acts like a dictionary. The following script proves this:
def f1(*arg):
print("arg is", arg)
print("Type of arg is ", type(arg))
def f2(**kwarg):
print("kwarg is", kwarg)
print("Type of kwarg is ", type(kwarg))
f1(1,2,3)
f2(a = 1, b = 2, c = 3)
5.4. Additional note on modules in Python
This topic consists of small scripts with explanations and so is not given here. Please refer to the book for this topic.
5.4.2. Using if __name__ == "__main__":
(Testing whether the script is being run directly or being imported by something else.)
This topic consists of small scripts needing detailed explanation and hence not covered here. Please refer to the book for this topic
5.5. Recursion
Recursion means “defining something in terms of itself”. It is a “divide and conquer” technique.
In Python, you can make a function call another function. In fact a function can even call itself.
The general structure of a recursive function in pseudo code can be given as follows:
# ---PSEUDO-CODE---
def recursiveFunction(attributes):
if (test for some_simple_case):
return (Simple computation without recursion)
else:
return recursive_solution
The program to calculate the factorial of a number is as follows:-
5.5.1 Recursive function to find factorial of a number
# Example of recursive function to calculate factorial of a positive integer
def factorRecurs(numb):
if numb == 1:
return 1
else:
print(numb)
return numb * factorRecurs(numb-1)
inpNum = int(input("Enter a number: "))
if inpNum >= 1:
print("The factorial of", inpNum, "is", factorRecurs(inpNum))
5.5.2. Recursive function to find a number is even or not
(Not very efficient)
You can test a number to be even or odd by recursion also. The steps are as follows:
The code is as follows:
def isEven(n):
if n <0: # negative numbers be made positive
n = -n
if n <2: # base condition when n is 0 or 1
if n == 0:
return True
else: # n must be 1 so number is odd
return False
else:
return (isEven(n-2))
print(isEven(-92))
5.5.3. Recursive function to find $a^b$
Another example. Finding the output of ab where a and b are positive integers.
Mathematically $a^b = a.a^{ab-1} = a.a.(a^{ab-2}) …… $
# Example of recursive function to calculate a ** b
def expF(b, e):
if e == 0: # Note the test is for 0 and not 1 as in previous cases
print("Exponent-> 0 so Terminating")
return 1
else:
print('Exponent is ->', e)
tempR = b * expF(b, e - 1)
print("For exp->", e, "Result->", tempR)
return tempR
myb = int(input("Enter the base number: "))
mye = int(input("Enter the exponent number: "))
if mye >= 1and mye >0:
print("The exponent->", myb, " raised to ->", mye, 'is ->',expF(myb, mye))
Another example of a recursive function to find GCD (Greatest Common Divisor) of two numbers using the Euclidean algorithm is as follows:
# Example of recursive function to calculate GCD (Greatest Common Divisor)
def rGCD(a, b):
print('Recursive GCD funct called with (', a, ',', b, ')' )
temp = b
b = a % b
if b == 0:
return temp
else:
intR = rGCD(temp, b)
return intR
fNo = int(input("Enter 1st number-> "))
sNo = int(input("Enter 2nd number-> "))
print("The GCD of", fNo, 'and ', sNo, "is", rGCD(fNo, sNo))
5.5.4. Recursive function to generate Fibonacci numbers
Let us see how recursion is used to generate Fibonacci numbers.
The Fibonacci series runs as follows:
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, …….
Mathematically, the series is defined as follows:
$Fn = F_{n-1} + F_{n-2}$
The seed values are $F_0 = 0$ and $F_1 = 1$.
So you can write:-
$\ F_n = \begin{cases} 0 & \quad \text{if } n \text{ = 0}\\ 1 & \quad \text{if } n \text{ = 1}\\ F_{n-1} & \quad \text{if } n \text{ > 1} \end{cases} $
The following script implements the generation of Fibonacci numbers using recursion as follows:
def fib(x):
if(x <= 1):
return x
else:
return(fib(x-1) + fib(x-2))
x = int(input("Enter number of terms:- "))
print("fib sequence:-")
for y in range(x):
print(fib(y),'', end='')
5.5.6. Recursion example: Tower of Hanoi
A recursive solution to the Tower of Hanoi can be understood as follows:
Moving ‘n’ disks from source rod to destination rod is equivalent to the following:-
So if $M(n)$ represents the total moves to shift ‘n’ disks from source to destination, then
$M(n) = 2 * M(n-1) + 1 $
Why? Because you have to move $M(n-1)$ disks twice, that is, once to the spare rod and then again to the target rod. Between these two movements, you have to move the nth disk to the target rod. It can be proved that for n disks $M(n) = 2n – 1$. Figure 1.3 in the book shows the steps involved for a Tower of Hanoi with five disks. The script to execute the algorithm can be outlined as follows:
[n, n-1, n-2, n-3, … 2, 1] where ‘n’ represents the number of the biggest disk and 1 represents the smallest disk. The script to implent this is shown below:-
count = 0
def toH(n, source, dest, extra):
global count
if n >0:
toH(n-1, source, extra, dest)# Move n-1 disks to extra as destination
if source: # If source list not empty
disk = source.pop()
count = count + 1
dest.append(disk)
print("status", source, extra, dest)
toH(n-1, extra, dest, source)
return count
n = 5
source = list(range(n, 0, -1))
moves = toH(n, source, [], [])
5.5.7. Memoizing example: Fibonacci series.
Memoizing is a technique in programming, where previously calculated results are used for future calculations.
print('Total moves->', moves)
Some points to remember about memoizing are as follows:
To calculate fib(5) you need to calculate fib(3) twice and fib(2) thrice. This is inefficient.
The following script shows how memoizing works:-
mem = {0:0 ,1:1} # A dictionary to hold fibonacci numbers generated earlier
def mFib(n): # n is the key of the dictionary
if n in mem:
return mem[n] # value corresponding to key n is returned
else:
mem[n] = mFib(n-1) + mFib(n-2) #Recursive call
return mem[n]
print(mFib(15))
print(mem)
5.6.1. zip function
The syntax of the function is:-
zip(*iterables)
The above syntax of the zip() function often creates confusion because of the use of “*”. The iterables can be containers like lists, tuples, strings etc
Following example shows how zip() may be used:-
# strings are iterables
# 2 strings of equal length
zstr = zip('abcd', 'efgh')
# Must cast it
print('zipped strings as list->', list(zstr))
# take 3 lists of unequal length
# zipping happens till shortest list is exhausted
zlist = zip([1, 2, 3, 4, 5, 6], ['a', 'b', 'c'], ['ant', 'bat'])
print('zipped lists as tuple->', tuple(zlist))
# zip 2 range() functions since they are iterable
zip_iterables = zip(range(1, 10, 2), range(20, 30))
print('zipped range functions->', list(zip_iterables))
5.6.2. Using zip to “unzip”
A common confusion with beginners is that the zip function can also be used for “unzipping”.
Suppose you have a zipped_list consisting of 2 items and you want to “extract” the items from this zipped list, then the syntax is:-
x, y = zip(*zipped_list)
In above x and y will get the 2 lists which are zipped up in the zipped_list Note that it was mentioned earlier that the syntax for the zip function was zip(*iterables). So note the following:-
This can be best understood by an example
caps = ['A', 'B', 'C', 'D']
smalls = ['a', 'b', 'c', 'd']
# Zip the above 2 lists
zip_result = zip(caps, smalls)
# Cast the zipped object to a list
zip_list = list(zip_result)
# Check that we have a zipped list of 2 lists
print('zip_list->', zip_list)
# Unzip the zipped list
cap_list, small_list = zip(*zip_list)
print('cap_list->', cap_list)
print('small_list->', small_list)
5.6.3 Lambda functions
In Python, you can write an “anonymous” function, that is, a function without a name. Note that a typical Python function (Or method) begins with the keyword ‘def’. However, a lambda function does not have a name. The syntax of lambda function is as follows:
lambda arguments: expression
There can be any number of arguments, but there can be only one expression. The following example shows the use of the lambda function.
# A normal function which squares a number
def square_numb(x):
return x ** 2
print(square_numb(10))
# A lambda function for squaring a Number
get_square = lambda x: x ** 2
print(get_square(20))
5.6.4. map() function
map() function takes a function and a sequence as its arguments.
It returns an iterator (Iterators are discussed later, but for the present, you can think of an iterator as some kind of a sequence over which you can “iterate” one by one).
The syntax of map() is:-
# First argument is function, second is an iterable
map_obj = map(function, iterable)
# There can be more than 1 iterable also
map_obj = map(function, iterable1, iterable2, iterable3........, iterableN)
Note that an iterable can be thought of as a sequence. So you can use a list, tuple, dictionary, and so on. You can even use a string since a string is also iterable in Python.
# Define a function which gives cube of a number
def cube_numb(n):
return n ** 3
# Create a list of numbers
numb_list = [1, 2, 3, 4, 5]
# Use map() to generate cubes of numbers in the list
cube_seq = map(cube_numb, numb_list)
# cube_seq is an object of map class. It is not a list
print(type(cube_seq))
# But you can cast a map object to list
print(list(cube_seq))
However, the real power of map() function lies in using it with lambda to generate “anonymous functions on the fly” and use them. The following code shows this:
# Take 2 lists. list1 has 5 items, list2 has 6 items
list1 = [1, 2, 3, 4, 5]
list2 = [6, 7, 8, 9, 10]
# Generate cubes of numbers in list1
cube_numbers = map(lambda x: x ** 3, list1)
print(list(cube_numbers))
# map function takes 1 function but 2 lists
# Note the 2 lists are of unequal length so only 5 not 6 items in output
add_lists = map(lambda x, y: x + y, list1, list2)
print(list(add_lists))
5.6.5. filter() function
filter() is a function to remove False items from a sequence.
A filter() function takes another function as its first argument and a sequence (Or rather an iterable) as its second argument. The first argument, that is, the function must return a Boolean value, that is, True or False.
Syntax of filter() is:-
# function must return a boolean True or False
filter(function, sequence)
Following code shows how filter may be used to get filter out odd numbers from a list. (Note that filter() function does not return a list object. If you need a list object, you need to cast it into a list:-
my_list = [ x for x in range(10)]
list_odds = filter(lambda x: x%2 == 0, my_list)
print(list(list_odds))
5.6.6. Generator functions
(Detailed discussion on generators is given in the book. Please refer to it.)
Consider the following code:
def myGen():
print('inside the generator')
yield 'a'# Yield a string
yield [1,2,3] # Yield a list
yield 3# Yield a number
# Use the generator function
count = 0
for x in myGen():
count = count + 1
print('Pass', count, '->', x)
The generator functions automatically implement the next() method in Python 2.x which is __next__() in Python 3.x. The implementation of __next__() is as follows:
def myGen():
print('inside the generator')
yield 'a'# Yield a string
yield [1,2,3] # Yield a list
yield 3# Yield a number
# Use the generator function
g = myGen()
print(g.__next__())
print(g.__next__())
print(g.__next__())
In Python 3.x you can also use the next() function as follows:
def myGen():
print('inside the generator')
yield 'a'# Yield a string
yield [1,2,3] # Yield a list
yield 3# Yield a number
# Use the generator function
g = myGen()
print(next(g))
print(next(g))
Infinite generators:- you can create an infinite generator as shown in the code below:-
def inf_gen(begin = 0):
while True:
yield begin
begin += 1
g = inf_gen(100)
print(g.__next__())
print(next(g))
You can modify the above generator function to generate a series of numbers starting from 1 upto a number given by the user as follows:
def my_gen(n):
val = 1
while val <= n:
yield val
val += 1
g = my_gen(5)
for count in range(5):
print(g.__next__())
Let us write a simple script which finds a prime number greater than a given number using a generator function. A prime number is an integer greater than 1 that has only 1 and itself as divisors.
def isPrime(myNum):
if myNum >1:
if myNum == 2: # 2 is prime
return True
if myNum % 2 == 0: # Even not prime
return False
for curNum in range(3, int(myNum **0.5) + 1, 2):
if myNum % curNum == 0:
return False
return True
return False # If myNum is not greater than 1 then False
def getPrime(myNum):
while True:
if isPrime(myNum):
yield myNum
myNum += 1
myP = getPrime(10)
for k in range(100): # Give 100 primes starting from 10 onwards
print(myP.__next__(), end = ' ')
5.8. Exercise
3. This exercise requires knowledge of Trapezoidal rule of numerical integration.
The value of a definite integral (that is, the area under the function) can be found using numerical integration. One common method for this is the Trapezoidal rule given by:
$Area= ∫_a^bf(x)dx ≈h[(\frac{1}{2})(f(a)+f(b))+ ∑_{i=1}^{n-1}f(a+ih)]\ where\ h= (\frac{b-a}{n}) $
Write a function which takes the following four parameters:
Also write a docstring for the function, which says:-
'''Calculates the definite integral of a function f(x), between the boundaries “a”, “b”, by dividing the area to “n” equal trapezoids/ strips'''
A sample program, which calculates
$∫_1^2 (\frac{1}{x})\ dx $ is shown as follows:
(Note : $∫_1^2 (\frac{1}{x})\ dx =ln(2)-ln(1)=ln(2))$
def trapez_integrate(f, a, b, n):
'''Calculates the numerical value of the definite integral of
a function f by dividing the interval from a to b into
n equal intervals.'''
# d is width of each interval
d = (b-a)/n
y = (1/2)*(f(a) + f(b))
# step over each interval
for m in range(1, n):
y = y + f(a + m * d)
area = d * y
return area
print('docstring of trapez_integrate()', trapez_integrate.__doc__)
# You can write your own function and then
# pass it to trapez_integrate()
def u(t):
return 1/t
# a is lower limit b is upper limit
a = 1; b = 2
# n is number of strips. Higher n gives more accurate result
n = 1000
area_a2b = trapez_integrate(u, a, b, n)
print('Area under 1/x from a to b->', area_a2b)
# Confirm that integral 1/x from a to b
# is equal to ln(2)
from math import *
print('ln(2)->', log(2))
4. Write a Python script, which uses list comprehension to generate a list of numbers from 97 to 122.
Then write a map() method, which generates a list of ASCII characters from the list of numbers.
Also write a ‘for’ loop, which uses map() function to iterate over the map object so as to print the ASCII characters one-by one.
Solution:
# Use list comprehension to create list of numbers from 97 to 122
# 97 to 122 are ASCII decimal codes for characters a to z
my_list = [x for x in range(97, 123)]
# Check the generated list
print(my_list)
my_charlist = map(chr, my_list)
# You can cast the map object to list
print(list(my_charlist))
# You can also iterate over a map object in a for loop
for each_char in map(chr, my_list):
print(each_char, end = '') # parameter end = '' prints without newline
5. The math module has a factorial function. Take a list of 10 numbers from 10 to 19 and use the map() method to generate factorials of the numbers in the list.
Solution:
import math
# Create list from 10 to 19
my_list = [x for x in range(10, 20)]
# Use map() to generate map object of factorials
list_factorials = map(math.factorial, my_list)
# Print but first cast the map object to list
print(list(list_factorials))
6. In maths, a power set of a set is a set, which has all the subsets of the original set. Note that here the word ‘set’ is used in the mathematical sense and not as a Python set. For instance, if you have a list [1, 2, 3] then you should generate [[], [1], [2], [3], [1, 2], [1, 3], [2, 3, [1, 2, 3]].
Note that if there are ‘n’ elements in the original list, then there will be 2n sublists. Write a script, which takes a list and creates a list which has as its members all the sublists of the original list.
# Function
def power_seq(a_seq):
a_list = [[]]
for x in a_seq:
a_list += [y + [x] for y in a_list]
return a_list
# Test
my_seq = {1, 3, 6, 2, 9}
print(power_seq(my_seq))
7. Given a list of numbers, write a script using anonymous function lambda() and filter() to filter out odd numbers.
Solution:
list1 = [x for x in range(10, 30)]
odd_filter = filter(lambda y: y % 2 == 1, list1)
# odd_filter is a filter object
print(odd_filter)
# If you want a list, you need to cast it to list
print(list(odd_filter))
9. Given the same list as in the above problem, write a script, which uses the map() function to generate a list of squares of the numbers in the given list.
list1 = [x for x in range(10, 30)]
map_squares = map(lambda x: x ** 2, list1)
# map_squares is a map object
print(map_squares)
# If you want list, cast it
print(list(map_squares))
10. Given a list of numbers, write a script which uses both filter() and map() to generate a list of squares of only even numbers in the given list.
Solution:
# list1 is list of numbers
list1 = [2, 6, 5, 7, 8, 10, 3, 3]
# even_filter is a filter object with only even numbers
even_filter = filter(lambda x: x % 2 == 0, list1)
# even_map uses lambda to square the numbers
even_map = map(lambda y: y ** 2, even_filter)
print(list(even_map))
14. Given a list of integers, use recursion to find the maximum (largest) number in the list.
Solution:
def largest(a_list):
if len(a_list) == 1:
return a_list[0]
else:
return max(a_list[0],largest(a_list[1:]))
# Test the function
my_list = [2, 6, 11, 33, 77, 19, 22, 99]
print(largest(my_list))
15. Again, use recursion to find the maximum number in a list.
However, don’t use loops (You may use ‘if-else’).
For this exercise, generate a list of 15 random integers in range 0 to 100 and then find the largest integer in this list.
Solution:
import random
# Generate a list of 15 integers in range 0 to 100
a_list=[random.randint(0,100) for r in range(15)]
print(a_list)
# Recursive function
def f_max(a_list):
if len(a_list) == 1:
return a_list[0]
else:
return max(a_list[0],f_max(a_list[1:]))
# Test the function
print(f_max(a_list))
16. Use recursion to multiply two numbers. You may use only operators addition or subtraction. (The numbers being multiplied may be 0, positive or negative)
Solution:
def recursive_product(m,n):
# return 0 if either m or n is 0
if(m == 0 or n == 0):
return 0
# Add m one by one
if(n > 0 ):
result = m + recursive_product(m, n - 1)
return result
# If n is negative
if(n < 0 ):
result = -(recursive_product(m, -n))
return result
# check
print('0 x 33 ->',recursive_product(0, 33)) # 0 x 33 -> 0
print('20 x 33 ->', recursive_product(20, 33)) # 20 x 33 -> 660
print('-5 x 10 ->', recursive_product(-5, 10)) # -5 x 10 -> -50
print('-5 x -10 ->', recursive_product(-5, -10)) # -5 x -10 -> 50
5.9. Beyond text book
1. Differentiating between an “iterable” and an “iterator ”
(Note:- some of the concepts used in this section relate to OOP concepts, such as classes and objects. So it may be better to do this section after doing those concepts)
A Python list is “iterable” because you can “iterate” over the individual items in a list. By the same logic, strings, tuples and other sequences and containers are all “iterable”. So if you have an “iterable” which could be a list, tuple, and so on, you can do the following:
# my_iterable stands for some Container
my_iterable = [1, 2, 3]
for each_item in my_iterable:
print(each_item) # Prints 1 2 3
In the above code, you are “iterating” over the “iterable” in the “for” loop.
However, behind the scene, the “for” loop in above code is doing the following:-
iter() method on the my_iterable, to convert it into an iterable object.next() method of this iterable object to iterate over each item in the container.next() method returns StopIteration error. So one can loop over a container, such as a list using iter() and next() methods as shown:
# my_iterable stands for some Container
my_iterable = [1, 2, 3]
my_iter = iter(my_iterable) # Calls my_iterable.__iter__()
# An exception will be thrown when the container
# runs out of items
# Use it to exit the infinite loop
while True:
try:
# Use next() to get next item
each_item = next(my_iter) # Calls my_iterable.__next__()
print(each_item)
except StopIteration:
print("breaking from infinite loop")
# On StopIteration break from loop
break
2. Making a generator function “behave” like an iterator
A generator function can be made to behave like an iterator, that is, it can be used in a “for” loop.
The following discussion shows how a “generator” function is used to create an iterator, which then is used to generate the Fibonnaci series.
The Fibonacci sequence has the following characteristics:
1,1, 2, 3, 5, 8 and so on, which is almost the same as previous case except the difference of 0. The following script generates the Fibonnaci series using a generator function as an iterator:
def myF(top):
f0, f1 = 0,1
while f0 <= top:
yield f0
f0, f1 = f1, f0 + f1
# Method 1 (Using __next__()
g = myF(100)
for var in range(10):
print(g.__next__(),' ', end = '')
# Method 2. The list() function can take an iterator as argument
# Since a generator is an iterator, you can give it as argument to list()
print(list(myF(100)))
4 Linear Congruential Generator
Python has modules for implementing Pseudo Random Number Generators (PRNG).
One of the oldest PRNG algorithms is the Linear Congruential Generator. It is given as follows:
$X_{n+1}= (a * X_n + c) mod\ m$,
$X_0$ is the start value.
Note here the values are m = 231, a = 1103515245, c = 12345. These values are typical for certain applications .
def seed_lcg(init_val= 1):
global new_seed
new_seed = init_val
def get_lcg():
multiplier = 1103515245
increment = 12345
modulo = 2 ** 31
global new_seed
new_seed = (multiplier * new_seed + increment) % modulo
return new_seed
seed_lcg(100)
for i in range(10):
print(get_lcg())
5. Partial unpacking of iterables
In Python you can do what may be called the “Partial unpacking of iterables”. This is shown in the following code:
# Partial unpacking of a list
x, y, *z = [1, 2, 3, 4]
print('x->', x)
print('y->', y)
print('z->', z)
# Partial unpacking of a tuple
a, b, c, *d = ('apple', 'bat', 'cat', 'dog', 1, 2, 3)
print('a->', a)
print('b->', b)
print('c->', c)
print('d->', d) #d gets rest of tuple items
Assignment
There are a number of “Pattern matching” or “string searching” algorithms available. The “search” involves a string to be searched in (Can be compared to a “haystack”) and a “pattern” to be found (Can be thought of as the “needle”).
A sample implementation of brute search algorithm (taken from the book) is as follows:
def brute_search(T, P):
'''Paremeters:-T is text, P is pattern
Returns: index i of beginning of match (If match found)
Returns -1 if no match'''
m = len(T)
n = len(P)
steps = m- n+ 1
# Do the search m - n + 1 times
for i in range(steps): #
x = 0 # x is an index for pattern P
while x < n and T[i + x] == P[x]:
x = x + 1
if x == n: # if you have reached the end of pattern,
return i # substring T[i: i+m] matches P
return - 1 # failed to find a match starting with any i
# Test
text = "abcabcaab"
pat = 'aab'
print(brute_search(text, pat))